namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0538. 把二叉搜索树转换为累加树")]
    public class No0538_ConvertBST : AbsBaseTestItem
    {
        /*
        给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        public override void OnTest()
        {
            Assert.TestExe(ConvertBST,
                new TreeNode(5)
                {
                    left = new TreeNode(2),
                    right = new TreeNode(13),
                },
                new TreeNode(18)
                {
                    left = new TreeNode(20),
                    right = new TreeNode(13),
                });
        }

        public TreeNode ConvertBST(TreeNode root)
        {
            int Sum = 0;
            TreeNode method(TreeNode node)
            {
                if (node == null) return node;
                method(node.right);
                Sum += node.val;
                node.val = Sum;
                method(node.left);
                return node;
            }
            return method(root);
        }
    }
}
